package cn.edu.jxau.test;

import java.io.IOException;
import java.util.Arrays;

/**
 * 快速排序优化
 * http://www.cnblogs.com/gw811/archive/2012/10/04/2711746.html
 * http://blog.csdn.net/scgaliguodong123_/article/details/46473365
 * http://blog.csdn.net/insistgogo/article/details/7785038
 * http://www.cnblogs.com/JeffreyZhao/archive/2009/03/26/tail-recursion-and-continuation.html
 * 
 * @author 付大石
 */
public class Main {

    public static void main(String[] args) throws IOException {

        int[] arr = { 79, 83, 83, 84, 56, 23, 67, 89, 23, 89, 45, 28, 34, 90, 23, 56, 34, 87, 54, 76, 32, 98 };
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] arr) {

        sort(arr, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int low, int high) {

        // 优化1：小规模数组转插入排序
//        if (high - low <= 7) {
//            for (int i = low; i <= high; i++) {
//                int j = i;
//                int temp = arr[j];
//                while (j - 1 >= low && temp < arr[j - 1]) {
//                    arr[j] = arr[j - 1];
//                    j--;
//                }
//                arr[j] = temp;
//            }
//            return;
//        }
        
        // 优化2：减小递归深度
        if(high <= low) return ;
        while(low<high) {
            int p = partition(arr, low, high);
            sort(arr, low, p - 1);
            low = p+1;
        }
    }

    private static int partition(int[] arr, int low, int high) {

        // 优化2：三取样切分
//        setPivotkey(arr, low, high);
        
//        int p = arr[low];
//        int i = low;
//        int j = high + 1;
//        while (i <= j) {
//            while (arr[++i] < p)
//                if (i >= high)
//                    break;
//            while (arr[--j] > p)
//                ;
//            if (i < j) {
//                swap(arr, i, j);
//            } else {
//                break;
//            }
//        }
//        swap(arr, low, j);
//        return j;
        
        // 优化3：减少交换次数
        int p = arr[low];
        while(low < high) {
            while(low<high && arr[high] >= p) {
                high--;
            }
            if(low < high) {
                arr[low] = arr[high];
                low++;
            }
            while(low<high && arr[low] <=p) {
                low++;
            }
            if(low < high) {
                arr[high] = arr[low];
                high--;
            }
        }
        System.out.println(low+"    "+high);
        arr[low] = p;
        return low;
    }

    /**
     * 优化选择pivotkey，从{@code arr}中选取最左，最右和中间三个数，找出中位数，
     * 放置在最左端，作为pivotkey。也可以随机取三个数找出中位数。
     * 
     * @param arr
     * @param low
     * @param high
     */
    private static void setPivotkey(int[] arr, int low, int high) {

        // 交换相应元素，是关系arr[mid] <= arr[low] <= arr[high]成立 //
        int mid = low + (high - low) / 2;
        if (arr[low] > arr[high]) { // 保证arr[low] <= arr[high]
            swap(arr, low, high);
        }
        if (arr[mid] > arr[high]) { // 保证arr[mid] <= arr[mid];
            swap(arr, mid, high);
        }
        if (arr[low] < arr[mid]) {
            swap(arr, low, mid);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
